Many real-life scenarios of problem-solving involve searching for an optimum combination or permutation of entities. The number of combinations although finite is usually very large to the extent that trying out all possible combinations is not an option. In the field of computer science, such problems are said to be computationally intractable and the process of searching is generally referred to as combinatorial optimization. Exact enumerative approaches tend to yield solutions of poor quality not withstanding the fact that the search process may incur high computational cost. Therefore, a class of stochastic algorithms, in particular, meta-heuristics, is useful for such combinatorial optimization problems. These are approximate methods with capacity to guarantee good quality solutions in reasonable time.
However, in order to fully capitalize on the potential capacity of meta-heuristics to solve real-life problems, one is required to have profound knowledge of algorithm design and coding, as well as domain-specific knowledge of the problems being addressed. Moreover, users may have different requirements and expectations on the performance of the algorithm according to different real-life scenarios. These may lead to significant differences in algorithm design and configurations. Without the necessary expertise of algorithm design, it is unlikely that an algorithm with satisfactory performance can be achieved.
Problem-solving environments with various optimization techniques including genetic algorithms have previously been presented. See U.S. Pat. Nos. 6,263,325, 6,086,617, Epogy Process Integration and Design Optimization Software, and the optimization software called Hierarchical Evolutionary Engineering Design System (HEEDS) software. These systems provide user-friendly interfaces for exploring various optimization tools for solving different optimization problems. This class of platforms facilitates the process of algorithm design and thus enhances the efficiency of problem-solving greatly. However, these software tools are essentially simulation environments. Though various algorithms can be configured and executed efficiently in these environments, the execution depends on the entire system. For many applications which require an embedded real-time solver, this class of environments does not offer the flexibility to configure an efficient stand-alone program, albeit a turnkey problem-solving algorithm.
In U.S. Pat. No. 6,286,017, a graphical environment is presented which assists users in generating a stand-alone application rapidly. It contains a modular library, which is managed by spreadsheet, and adopts other software re-use technology. Users are able to retrieve procedures from the library with the friendly GUI it provides. Based on the procedures selected, a stand-alone application is generated automatically. However, this invention only addresses the programming issue. It does not involve any algorithm design knowledge. Therefore, it may not meet the needs of solution methodology when complex algorithms like meta-heuristics need to be developed.
TOMLAB is a general optimization environment in MATLAB. It is essentially a MATLAB toolbox, which encapsulates various optimization procedures, including complex meta-heuristics like genetic algorithms. It supposedly makes it easier for users to retrieve the integrated procedures and routines to build up an application in the form of source codes. However, it cannot generate source codes automatically and the user has to deal with a functional programming language, i.e. MATLAB programming language. This is a big obstacle for users who may not be familiar with MATLAB language. Furthermore, it requires the support of an expensive third party software environment, i.e. MATLAB.
Easy Specification of Evolutionary Algorithm (EASEA) is a high-level script language dedicated to the specification of evolutionary algorithms (EA). It retrieves various EA procedures and routines from well-known EA libraries: GALib and EQ. Users compose the .ez file in EASEA language for configuring an evolutionary algorithm. The .ez file is then compiled by EASEA compiler to C++ files. The generated C++ files are in turn compiled and linked with the corresponding library to produce an executable file implementing the evolutionary algorithm specified in the original .ez file. This way, the most tedious codes generation job in algorithm development is avoided. Therefore the efficiency of application development is enhanced significantly. However both EASEA and another similar language, Evolutionary Algorithm Modeling Language (EAML), are still forms of text-based language, although they are higher level than any functional programming language. These two script languages both require a specifically designed compiler to translate the script language to a functional programming language. Furthermore, it is necessary for general users to be familiar with the syntax of the language.
An important point to be made is that none the prior arts introduced above address the issue of automatically configuring an algorithm that is optimal for a given class of problems that it is intended to solve. The quality of the resulting solution method depends very much on the experience and the expertise of the programmer or system' developer. More importantly, there are no mechanisms for learning based on samples of test problems.
In the technical paper of M. Birrattari, et al. (2002), a racing algorithm was proposed for configuring the parameters of meta-heuristics. Though the resulting ACO algorithm is human competitive, this proposed racing algorithm is only able to tune real number parameters in the meta-heuristics and it fails to address other configurations issues, like structures, procedure selections and so on.
In the technical paper of K. O. Stanley et al. (2005), an evolutionary system, namely NERO, was proposed. It encodes the neural networks as artificial chromosomes and uses a genetic algorithm to evolve the chromosomes (i.e. neural networks) for the purpose of a real-time game. It optimizes not only the parameter settings, but also the topological structures of the neural networks. It is also able to adjust the neural networks according to dynamic changes of the game scenarios in real time. NERO achieves human competitive results and addresses the needs of quick generation of complex systems (i.e., neural networks in this case) with excellent performance. However, NERO is dedicated to neuro-evolution. It does not address the issue of evolving other general meta-heuristic algorithms for a wider scope of problem-solving needs.
In U.S. Pat. Nos. 5,867,397, 6,360,191 and 6,532,453, J. Koza proposed a novel problem-solving technology, namely genetic programming. It encodes a solution method or system (codes of a computer program) into a tree based artificial chromosome and then adopts the operations in genetic algorithm to evolve the chromosomes (i.e. the solution methods program). Genetic programming not only optimizes the parameter settings, but also the structures of the solution method for a given problem. Genetic programming has successfully produced many human-competitive results in a very wide range of real-life applications. However so far, it has only proven applicable to relatively simple systems, like curve-function approximation, RLC circuits design or even a programming problem as issued in U.S. Pat. No. 6,327,582. It does not address the need of automatic configuration of meta-heuristic algorithms for general optimization purposes in real-life applications.